package Lee_code;

/**
 * @author blh
 * @date 2024年07月01日 10:52
 */
public class Lee_240_71 {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 先找列再找行
        int rleft = 0, rright = matrix.length - 1;
        int lleft = 0, lright = matrix[0].length - 1;
        int column = 0;
        int row = 0;

        // 先找列, 偏左
        while (lleft <= lright) {
            int mid = lleft + (lright - lleft) / 2;
            if (matrix[0][mid] > target) {
                lright = mid - 1;
            } else if (matrix[0][mid] < target) {
                column = lleft;
                lleft = mid + 1;
            } else if (matrix[0][mid] == target) {
                return true;
            }
        }
        // 再找行
        while (rleft <= rright) {
            int mid = rleft + (rright - rleft) / 2;
            if (matrix[mid][column] > target) {
                rright = mid - 1;
            } else if (matrix[mid][column] < target) {
                row = lleft;
                rleft = mid + 1;
            } else if (matrix[mid][column] == target) {
                return true;
            }
        }

        lleft = 0;
        lright = matrix[0].length - 1;

        while (lleft <= lright) {
            int mid = lleft + (lright - lleft) / 2;
            if (matrix[row][mid] > target) {
                lright = mid - 1;
            } else if (matrix[row][mid] < target) {
                column = lleft;
                lleft = mid + 1;
            } else if (matrix[row][mid] == target) {
                return true;
            }
        }
        return false;
    }
}
